package skiplist;

import java.util.Random;
import java.util.Stack;
/*
模拟实现：跳表
允许重复值
 */
class Skiplist {
    // 跳表结点
    private static class SkipNode {
        int val;
        SkipNode right;
        SkipNode down;
        public SkipNode(int val) {
            this.val = val;
        }
        public SkipNode() {}
    }

    // 跳表头结点
    private SkipNode highHead ;                 // 最上层的头节点
    private Random random ;                     // 随机因子
    private static final int MAX_LEVEL = 32;    // 最高就 32 层
    private int highLevel;                      // 当前有多少层

    public Skiplist() {
        highHead = new SkipNode(Integer.MIN_VALUE); // 头节点最小
        random = new Random();
        highLevel = 0;
    }

    // 查找某个结点，如果存在，返回结点；否则返回 空结点
    public SkipNode search(int tar) {
        SkipNode cur = highHead;
        while (cur != null) {
            if (cur.right == null) { // 如果为空，只能往下走
                cur = cur.down;
            } else if (cur.right.val == tar) { // 如果相等
                return cur.right;  // 返回即可
            } else if (cur.right.val > tar) { // 找到第一个大于它的结点
                cur = cur.down;    // 往下走
            } else {                          // 否则就是小于，小于只能继续往右走
                cur = cur.right;
            }
        }
        return null;
    }

    // 删除一个结点
    public boolean remove(int tar) {
        // 思路和查找差不多，一边找一边删
        SkipNode cur = highHead;
        boolean isDel = false;
        while (cur != null) {
            if (cur.right == null) {
                cur = cur.down;
            } else if (cur.right.val == tar) {
                cur.right = cur.right.right;  // 删除
                isDel = true;
                cur = cur.down; // 往下走，继续往下删除
            } else if (cur.right.val > tar) {  // 第一个大于
                cur = cur.down; // 往下走
            } else {
                cur = cur.right; // 找不到，往右走
            }
        }
        return isDel;
    }

    // 插入一个结点
    public void insert(int num) {
        Stack<SkipNode> stk = new Stack<>(); // 栈：存储寻找路径的结点，同时需要为其后新增结点
        SkipNode cur = highHead;
        while (cur != null) {
            if (cur.right == null) { // 右结点为空，往下走
                stk.push(cur);
                cur = cur.down;
            } else if (cur.right.val >= num) { // 第一个大于的点，往下走, 或者 等于
                stk.push(cur);
                cur = cur.down;
            } else {
                cur = cur.right;
            }
        }

        // 然后在「路径」中的结点后面都加上该结点
        // 再根据随机算法计算是否要添加索引
        SkipNode prevNode = null; // 前驱结点
        int curLevel = 1; // 当前层数
        while (!stk.isEmpty()) {
            SkipNode top = stk.pop();
            SkipNode newNode = new SkipNode(num);

            newNode.right = top.right;
            top.right = newNode;

            newNode.down = prevNode;
            prevNode = newNode;

            if (curLevel > MAX_LEVEL) { // 达到上限层数
                break;
            }
            double choice = random.nextDouble(); // 生成 [0,1]之间的随机数
            if (choice > 0.5) { // 大于 0.5 就结束，否则继续向上增加索引
                break;
            }

            curLevel ++;
            if (curLevel > highLevel) { // 如果达到了新高度
                SkipNode newHead = new SkipNode(Integer.MIN_VALUE);
                newHead.down = highHead;
                highHead = newHead; // 新的头结点

                stk.push(highHead);
                highLevel = curLevel; // 更新高度
            }
        }
    }
}
